package Leetcode第一期;

/**
 * @author : K k
 * @date : 10:51 2020/9/11
 * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 *输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
 */
public class 复杂链表的复制_35 {
    public Node copyRandomList(Node head) {
        if (head==null){return null;}

        for(Node node=head;node!=null;node=node.next.next){
            //复制一遍链表
            Node temp=node.next;
            node.next=new Node(node.val);
            node.next.next=temp;
        }

        //将random也复制
        for (Node node=head ;node != null;node=node.next.next){
            if (node.random!=null){
                node.next.random=node.random.next; //由于node.random的复制项是node.random.next
            }
        }

        Node newHead=head.next; //新开头
        //取出新构造的链表
        for(Node node=head;node!=null&&node.next!=null;){
            Node tmp=node.next;
            node.next=tmp.next;
            node=tmp;
        }
        return newHead;
    }
}
